#ifndef TREE_H
#define	TREE_H

#include <cstdlib>
#include <cassert>
#include <climits>
#include <exception>

//Generic max
template <class T>
T ourMax(const T& x, const T& y) {
	return x > y ? x : y;
}

template <class T>
T ourMin(const T& x, const T& y) {
	return x < y ? x : y;
}

template <class T>
T ourMin(const T& x, const T& y, const T& z) {
	return ourMin(ourMin(x, y), z);
}
//TODO: delete this:
//template <class T>
//T ourMin(const T& x, const T& y, const T& z) {
//	if (x < y) {
//		if (x < z) {
//			// x < z, x < y
//			return x;
//		}
//		// z <= x < y
//		return z;
//	}
//	if (y < z) {
//		// y <= x, y < z
//		return y;
//	}
//	// z <= y <= x
//	return z;
//}

class TreeException: public std::exception{};

class ElementAlreadyExistsException: public TreeException{};
class NoSuchElementException: public TreeException{};

const int EMPTY_SON_HEIGHT = -1;

/*
Assumptions:
	- T has operator<, operator==, operator!=
	- T has a C'Ctor
	-T has int getId() function
 */
template <class T>
class AvlTree {
private:
	/*-----------SubClasses-----------*/
	struct TreeNode {
		// Fields
		T* data;
		int min;
		TreeNode* leftSon;
		TreeNode* rightSon;
		TreeNode* parentNode;
		int height;

		// C'tors
		TreeNode(const T& data, TreeNode* parentNode) :
			data(new T(data)),
			min(data.getId()),
			leftSon(NULL),
			rightSon(NULL),
			parentNode(parentNode),
			height(0) { };
		// especially for creating dummy node:
		TreeNode() :
			data(NULL),
			min(INT_MIN),
			leftSon(NULL),
			rightSon(NULL),
			parentNode(NULL),
			height(0) { };

		~TreeNode() {
			delete data;
		}

		/* Copy C'tor and operator= were not implemented since there is no
		 * immediate / obvious interpretation to their action when it comes to
		 * a tree node.
		 */

		void updateHeight() {
			if ((NULL == leftSon) && (NULL == rightSon)) {
				height = 0;
			}
			else if (NULL == leftSon) {
				height = 1 + rightSon->height;
			}
			else if (NULL == rightSon) {
				height = 1 + leftSon->height;
			}
			else {
				height = 1 + ourMax(leftSon->height, rightSon->height);
			}
		}

		int getBF() const {
			int leftSonHeight = leftSon ? leftSon->height : EMPTY_SON_HEIGHT;
			int rightSonHeight = rightSon ? rightSon->height : EMPTY_SON_HEIGHT;
			return leftSonHeight - rightSonHeight;
		}

		//Methods - TreeNode
		bool operator<(const TreeNode& nodeToCompareTo) const {
			if (NULL == data) {
				/* this is a dummy node, which counts as the node
				 * with the largest data.
				 */
				return false;
			}
			if (NULL == nodeToCompareTo.data) {
				/* nodeToCompareTo is a dummy node, which counts as the node
				 * with the largest data.
				 */
				return true;
			}
			return (*data < *(nodeToCompareTo.data));
		}

		bool operator==(const TreeNode& nodeToCompareTo) const {
			return (!(*this < nodeToCompareTo) && !(nodeToCompareTo < *this));
		}

		bool operator!=(const TreeNode& nodeToCompareTo) const {
			return !(*this == nodeToCompareTo);
		}
	};

	/*-------------Vars-------------*/
	/* mainRoot is a dummy node, which is considered the node with the largest
	 * data. Therefore it might have only a left son.
	 */
	TreeNode* mainRoot;
	int size;

	/*-----------Methods------------*/
	void _deleteTree(TreeNode* root);
	TreeNode& _findAux(const T& obj, TreeNode& root);
	TreeNode& _findLastNodeInPath(const T& object);

	void _updateMin(TreeNode& nodeToUpdate);

	void _removeNode(TreeNode& nodeToRemove);

	TreeNode& _rotate(TreeNode& oldRoot, bool isRotateRight);
	TreeNode& _rotateLeft(TreeNode& root);
	TreeNode& _rotateRight(TreeNode& root);
	TreeNode& _LL_Rotation(TreeNode& node);
	TreeNode& _RR_Rotation(TreeNode& node);
	TreeNode& _LR_Rotation(TreeNode& node);
	TreeNode& _RL_Rotation(TreeNode& node);

	TreeNode& _balanceNode(TreeNode& node);
	void _balanceTree(TreeNode* node);

public:
	// C'tor and D'tor
	AvlTree() : mainRoot(new TreeNode), size(0) {}
	~AvlTree();

	// DECLERATIONS - sub-classes and friends

	// METHODS
	void insert(const T& data);
	const T* find(const T& data);
	void remove(const T& data);
	int getSize() const;
	int getHeight() const;
	int findMinFrom(const T& data);
};
/* ===== END CLASS AvlTree ===== */

/* EXTERNAL METHODS IMPLEMENTATION - AvlTree */

template <class T>
void AvlTree<T>::_deleteTree(TreeNode* root) {
	if (NULL == root) {
		return;
	}

    _deleteTree(root->leftSon);
    _deleteTree(root->rightSon);
    delete root;
}

template <class T>
AvlTree<T>::~AvlTree() {
	_deleteTree(mainRoot);
}

/**
 * _findAux: Auxiliary find function, recursive.
 *
 * @param obj:  The key-data object we want to find.
 *              This would most probably be a dummy object.
 *
 * @param root: The root of the sub-tree we want to search in.
 *
 * @return:     If the key is in the tree: returns the node holding it.
 *              If not - returns the last node on the search trail.
 */
template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_findAux(const T& obj,
		TreeNode& root) {
	if ((NULL != root.data) && (*(root.data) == obj))
		return root;
	// (NULL == root.data) means (root == mainRoot)
	else if (((NULL == root.data) || (obj < *(root.data)))
			&& (root.leftSon != NULL))
		return _findAux(obj, *(root.leftSon));
	else if ((NULL != root.data) && (*(root.data)< obj)
			&& (root.rightSon != NULL))
		return _findAux(obj, *(root.rightSon));
	return root;
}

template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_findLastNodeInPath(const T& obj) {
	return _findAux(obj, *mainRoot);
}

template <class T>
void AvlTree<T>::_updateMin(TreeNode& nodeToUpdate) {
	int leftMin = INT_MAX;
	int rightMin = INT_MAX;

	if (NULL != nodeToUpdate.leftSon) {
		leftMin = nodeToUpdate.leftSon->min;
	}
	if (NULL != nodeToUpdate.rightSon) {
		rightMin = nodeToUpdate.rightSon->min;
	}
	nodeToUpdate.min = ourMin(nodeToUpdate.data->getId(), leftMin, rightMin);
}

template <class T>
void AvlTree<T>::_removeNode(TreeNode& nodeToRemove) {
   //No sons
	if ((nodeToRemove.leftSon == NULL) && (nodeToRemove.rightSon == NULL)){
		if (nodeToRemove < *(nodeToRemove.parentNode))
			nodeToRemove.parentNode->leftSon = NULL;
		else
			nodeToRemove.parentNode->rightSon = NULL;
	}

	//One son
	else if ((nodeToRemove.leftSon == NULL) != (nodeToRemove.rightSon == NULL)){
		 // This means: (has left son) XOR (has right son)
		TreeNode* sonNodePtr = NULL;
		if (nodeToRemove.leftSon != NULL)
			sonNodePtr = nodeToRemove.leftSon;
		else
			sonNodePtr = nodeToRemove.rightSon;
		// connecting nodeToRemove's son and parent nodes.
		sonNodePtr->parentNode = nodeToRemove.parentNode;
		if (nodeToRemove < *(nodeToRemove.parentNode))
			nodeToRemove.parentNode->leftSon = sonNodePtr;
		else
			nodeToRemove.parentNode->rightSon = sonNodePtr;
	}

	//Two sons
	else { // ((nodeToRemove.leftSon != NULL) && (nodeToRemove.rightSon != NULL))
		// nextNode will hold the next largest node.
		TreeNode* nextNode = nodeToRemove.rightSon;
		while (nextNode->leftSon != NULL){
			nextNode = nextNode->leftSon;
		}

		delete nodeToRemove.data;
		nodeToRemove.data = new T(*(nextNode->data));
		/* Removing the next node, which has up to 1 son, instead of removing
		 * nodeToRemove (which now consists nextNode's data).
		 */
		_removeNode(*nextNode);
		return;
	}

	//Remove and call balancing function
	TreeNode* parentNode = nodeToRemove.parentNode;
	delete &nodeToRemove;
	size--;

	// Updating min field of nodeToRemove's ancestors
	for (TreeNode* nodeToUpdate = parentNode;
		nodeToUpdate != mainRoot;
		nodeToUpdate = nodeToUpdate->parentNode) {
		_updateMin(*nodeToUpdate);
	}

	_balanceTree(parentNode);
}

template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_rotate(TreeNode& oldRoot,
		bool isRotateRight) {
    AvlTree<T>::TreeNode& newRoot = isRotateRight ? *(oldRoot.leftSon) :
    		*(oldRoot.rightSon);

	if (isRotateRight) {
		// Connecting newRoot's rightSon as oldRoot's leftSon
		oldRoot.leftSon = newRoot.rightSon;
		if (NULL != oldRoot.leftSon) {
    		oldRoot.leftSon->parentNode = &oldRoot;
    	}

	} else {
		// Connecting newRoot's leftSon as oldRoot's rightSon
		oldRoot.rightSon = newRoot.leftSon;
		if (NULL != oldRoot.rightSon) {
			oldRoot.rightSon->parentNode = &oldRoot;
		}
	}

    // Connecting newRoot to its new parent which was before oldRoot's parent)
    newRoot.parentNode = oldRoot.parentNode;
    if (oldRoot.parentNode->leftSon == &oldRoot) {
    	oldRoot.parentNode->leftSon = &newRoot;
    }
    else { //oldRoot.parentNode->rightSon == oldRoot
    	oldRoot.parentNode->rightSon = &newRoot;
    }

    // Connecting oldRoot to newRoot
    if (isRotateRight) {
    	newRoot.rightSon = &oldRoot;
    } else {
    	newRoot.leftSon = &oldRoot;
    }
    oldRoot.parentNode = &newRoot;

    oldRoot.updateHeight();
    newRoot.updateHeight();

	// Updating min field of oldRoot and newRoot
	_updateMin(oldRoot);
	_updateMin(newRoot);

    return newRoot;
}

template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_rotateLeft(TreeNode& root) {
    return _rotate(root, false);
}

template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_rotateRight(TreeNode& root) {
    return _rotate(root, true);
}

template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_LL_Rotation(TreeNode& node) {
	return _rotateRight(node);
}
	
template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_RR_Rotation(TreeNode& node) {
	return _rotateLeft(node);	
}
	
template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_LR_Rotation(TreeNode& node) {
	_rotateLeft(*(node.leftSon));
	return _rotateRight(node);
}

template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_RL_Rotation(TreeNode& node) {
    _rotateRight(*(node.rightSon));
	return _rotateLeft(node);
}

/**
 * Description: Performs the appropriate rotation for node,
 * 				according to the BFs.
 * input:		node - The node to be rotated - it should have a BF of 2 or -2.
 * exceptions:	none
 */
template <class T>
typename AvlTree<T>::TreeNode& AvlTree<T>::_balanceNode(TreeNode& node) {
	if (2 == node.getBF()){
		if (-1 == node.leftSon->getBF()) {
			return _LR_Rotation(node);
		}
		else { // node.leftSon->getBF() >= 0
	 		return _LL_Rotation(node);
	 	}
	} else if (-2 == node.getBF()){
	 	if (1 == node.rightSon->getBF()) {
	 		return _RL_Rotation(node);
	 	}
	 	else { // node.rightSon->getBF() <= 0
	 		return _RR_Rotation(node);
        }
	} else {
		assert(false);
		return node;
	}
}

/**
 * Description: Balances all the ancestors of node.
 * input: 		deepestNode - the "deepest" node in the insert/remove path
 * 				(a leaf which is either a node that has just been inserted,
 * 				or a node connected to a node that has been removed).
 * exceptions:	none
 */
template <class T>
void AvlTree<T>::_balanceTree(TreeNode* deepestNode) {
	for (TreeNode* node = deepestNode;
			node != mainRoot;
			node = node->parentNode) {
		int oldSubTreeHeight = node->height;
		node->updateHeight();
		if (2 == std::abs(node->getBF())) {
			/* Balancing currentNode's BF, and updating node to point to
			 * the new root of the current sub-tree.
			 */
			node = &(_balanceNode(*node));
		}
		if (oldSubTreeHeight == node->height) {
			/* If the current node's height remained unchanged, either because
			 * it was unchanged or because a rotation restored it to its height
			 * before the tree was changed - we do not need to carry on fixing
			 * ancestors. The tree is now fully balanced.
			 */
			break;
		}
	}
}

/*
 * exceptions: 	ElementAlreadyExistsException - if there is already an element
 * 						with the required data in the tree.
 */
template <class T>
void AvlTree<T>::insert(const T& data) {
	TreeNode& lastNode = _findLastNodeInPath(data);

	if ((NULL != lastNode.data) && (*(lastNode.data) == data)) {
		throw ElementAlreadyExistsException();
	}

	TreeNode* newNode = new TreeNode(data, &lastNode);
	if (lastNode < *newNode) {
		assert(NULL == lastNode.rightSon);
		lastNode.rightSon = newNode;
	}
	else { // (lastNode > *newNode)
		assert(NULL == lastNode.leftSon);
		lastNode.leftSon = newNode;
	}
	size++;

	// Updating min field of newNode's ancestors
	for (TreeNode* nodeToUpdate = &lastNode;
		nodeToUpdate != mainRoot;
		nodeToUpdate = nodeToUpdate->parentNode) {
		_updateMin(*nodeToUpdate);
	}

	_balanceTree(&lastNode);
}

template <class T>
/* returns a pointer to const data rather than a copy of the data,
 * since we might have to return NULL if the data is not found in the tree.
 * exceptions: none
 */
const T* AvlTree<T>::find(const T& data) {
	TreeNode& foundNode = _findLastNodeInPath(data);
	if ((NULL == foundNode.data) || (data != *(foundNode.data))) {
		return NULL;
	}
	return foundNode.data;
}

/**
 * remove: removes a node holding the given key, then balances the tree.
 * @param data: The key to remove. Should probably be a dummy element of type T.
 * exceptions: 	NoSuchElementException - if there is no element with the
 * 										 required data in the tree
 */
template <class T>
void AvlTree<T>::remove(const T& data) {
    TreeNode& nodeToRemove = _findLastNodeInPath(data);
   
    //Node not found
    if ((NULL == nodeToRemove.data) || (data != *(nodeToRemove.data)))
        throw NoSuchElementException();
    
    _removeNode(nodeToRemove);
}

template <class T>
int AvlTree<T>::getSize() const {
	return size;
}

template <class T>
int AvlTree<T>::getHeight() const {
	if (NULL == mainRoot->leftSon) {
		// No Nodes in tree except for the dummy mainRoot node.
		return EMPTY_SON_HEIGHT;
	}
	return mainRoot->leftSon->height;
}

template <class T>
int AvlTree<T>::findMinFrom(const T& data) {
	TreeNode* foundNode = &(_findLastNodeInPath(data));
	if (NULL == foundNode->data) {
		/* This means there are no nodes in the tree but the mainRoot 
		   dummy node.
		 */
		throw NoSuchElementException();
	}
	
	int minFrom = INT_MAX;
	bool isThereBigger = false;
	for (; mainRoot != foundNode; foundNode = foundNode->parentNode) {
		if ((data < *(foundNode->data)) || (data == *(foundNode->data))){
			isThereBigger = true;
			int rightMin = INT_MAX;
			if (NULL != foundNode->rightSon) {
				rightMin = foundNode->rightSon->min;
			}
			minFrom = ourMin(minFrom, 
				foundNode->data->getId(),
				rightMin);
		}
		
	}

	if (!isThereBigger) {
		throw NoSuchElementException();
	}
	return minFrom;
}

/* ===== END EXTERNAL TREE IMPLEMENTATION ===== */

#endif	/* TREE_H */
